Черный Ящик
представляет собой примитивную базу даных. Он может хранить массив целых чисел, а также
имеет специальную переменную i. В
начальный момент Черный Ящик пустой, переменная i равна 0. Черный Ящик обрабатывает последовательность команд
(транзакций). Существует два типа транзакций:
ADD(x): положить
элемент x в Черный Ящик;
GET: увеличить i
на 1 и вывести i-ый минимальный
элемент среди всех чисел, находящихся в Черном Ящике;
Помните,
что i-ый минимальный элемент
находится на i-ом месте после того
как все элементы черного ящика будут отсортированы в неубывающем порядке.
Рассмотрим
работу Черного Ящика на примере:
|
шаг |
операция |
i |
содержимое
черного ящика |
результат |
|
1 |
ADD(3) |
0 |
3 |
|
|
2 |
GET |
1 |
3 |
3 |
|
3 |
ADD(1) |
1 |
1, 3 |
|
|
4 |
GET |
2 |
1, 3 |
3 |
|
5 |
ADD(-4) |
2 |
-4, 1, 3 |
|
|
6 |
ADD(2) |
2 |
-4, 1,
2, 3 |
|
|
7 |
ADD(8) |
2 |
-4, 1,
2, 3, 8 |
|
|
8 |
ADD(-1000) |
2 |
-1000,
-4, 1, 2, 3, 8 |
|
|
9 |
GET |
3 |
-1000,
-4, 1, 2, 3, 8 |
1 |
|
10 |
GET |
4 |
-1000,
-4, 1, 2, 3, 8 |
2 |
|
11 |
ADD(2) |
4 |
-1000,
-4, 1, 2, 2, 3, 8 |
|
Необходимо
разработать эффективный алгоритм выполнения заданной последовательности
транзакций. Максимальное количество транзакций ADD и GET равно 30000
(каждого типа).
Опишем
последовательность транзакций двумя целочисленными массивами:
1. A(1),
A(2), ..., A(m): последовательность
элементов, которая будет добавляться в Черный Ящик. Элементами являются целые
числа, по модулю не большие 2 000 000 000, m
≤ 30000. Для выше описанного примера A = (3, 1, -4, 2, 8, -1000, 2).
2. u(1),
u(2), ..., u(n): последовательность
указывает на количество элементов в Черном Ящике в момент выполнения первой,
второй, ... n-ой транзакции GET. Для
выше описанного примера u = (1, 2, 6, 6).
Работа
Черного Ящика предполагает, что числа в последовательности u(1), u(2), ..., u(n) отсортированы в неубывающем порядке, n ≤ m, а для каждого p (1
≤ p ≤ n) имеет место неравенство p ≤ u(p) ≤ m. Это следует
из того, что для p-го элемента
последовательности u мы выполняем GET транзакцию, которая выводит p-ый минимальный элемент из набора чисел
A(1), A(2), ..., A(u(p)).
Вход. Состоит из следующего набора чисел: m, n,
A(1), A(2), ..., A(m), u(1), u(2),
..., u(n). Все числа разделены
пробелами и (или) символом перевода на новую строку.
Выход. Вывести ответы Черного Ящика на
последовательность выполненных транзакций. Каждое число должно выводиться в
отдельной строке.
|
Пример входа |
Пример выхода |
|
7 4 3 1 -4 2 8 -1000 2 1 2 6 6 |
331
2 |
структуры данных - set
Анализ алгоритма
Объявим мультимножество
s, занесем в него некоторый максимальный
элемент (например 2000000000) и установим на него указатель iter. Далее будем обрабатывать числа
так, чтобы итератор iter всегда
указывал на i-ый минимальный элемент
среди всех чисел, находящихся в Черном Ящике.
Заносим в
мультимножество числа последовательности A[i].
Если текущее заносимое число A[i]
меньше того, на которое указывает iter,
то уменьшаем iter на 1. Иначе iter остается без изменения. С выводом
каждого числа u[i] увеличиваем iter на 1. Таким образом iter постоянно указывает на элемент,
возвращаемый при операции get.
Реализация алгоритма
Последовательность
чисел A[1], …, A[m], которая заносится в черный ящик,
храним в массиве mas. Черный ящик хранится в переменной s типа мультимножество.
int mas[30001];
multiset<int> s;
multiset<int>::iterator iter;
Основной
цикл программы. Обнуляем черный ящик s.
Читаем входные данные.
s.clear();
scanf("%d %d",&m,&n);
for(i = 0; i
< m; i++) scanf("%d",&mas[i]);
Занесем в s максимальное число для удобства его
дальнейшего использования. Установим указатель iter на начало черного ящика – минимальный элемент, хранящийся в
нем. В переменной ptr храним
количество чисел, занесенных в черный ящик.
s.insert(2100000000);
iter = s.begin(); ptr = 0;
for(i = 0; i < n; i++)
{
Читаем значение
u[i]. Для вывода результата на
очередной запрос get, необходимо просто вывести значение, на которое указывает iter. Но при этом в черном ящике должно
находиться u[i] чисел. Если до этого в
ящик было занесено менее u[i] чисел (ptr < u), то заносим их последовательно, уменьшая на 1 указатель iter каждый раз когда очередное значение
m[ptr] меньше того, на которое
указывает iter.
scanf("%d",&u);
while(ptr < u)
{
s.insert(mas[ptr++]);
if (mas[ptr-1] < *iter) iter--;
}
printf("%d ",*iter);iter++;
}